{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 6 计算和控制流（二）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.斐波拉契数列：这个数列从第三项开始，每一项都等于前两项之和。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "已知斐波拉契数列的前两项都是1，我们定义求斐波拉契数列的第n项（n<=50）的函数为fbnq，程序主体如下：\n",
    "\n",
    "```python\n",
    "\n",
    "n=int(input(\"\"))\n",
    "print(fbnq(n))\n",
    "\n",
    "```\n",
    "\n",
    "请补充完成对fbnq函数的定义。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共一行，为一个正整数。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，为一个正整数。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "```\n",
    "7\n",
    "```\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "```\n",
    "13\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 解法 1：正常思路"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 8\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21\n"
     ]
    }
   ],
   "source": [
    "def fbnq(n):\n",
    "    if n <= 2:  # 前两项为 1\n",
    "        return 1\n",
    "    else:\n",
    "        a1 = 1\n",
    "        a2 = 1\n",
    "        for i in range(n - 2):\n",
    "            a3 = a1 + a2\n",
    "            a1 = a2\n",
    "            a2 = a3\n",
    "        return a3\n",
    "\n",
    "\n",
    "n = int(input(\"\"))\n",
    "print(fbnq(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 解法 2：递归\n",
    "\n",
    "递归虽然非常易于理解，但非常占用计算资源，性能不是特别好。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 9\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "34\n"
     ]
    }
   ],
   "source": [
    "def fbnq(n):\n",
    "    if n <= 2:  # 前两项为 1\n",
    "        return 1\n",
    "    else:\n",
    "        return fbnq(n - 1) + fbnq(n - 2)\n",
    "    \n",
    "    \n",
    "n = int(input(\"\"))\n",
    "print(fbnq(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.求两个数的最大公约数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "输入两个正整数num1和num2（不超过1000），求它们的最大公约数并输出。\n",
    "\n",
    "我们定义求最大公约数的函数为hcf，给出程序主体如下：\n",
    "\n",
    "```python\n",
    "\n",
    "num1=int(input(\"\"))\n",
    "num2=int(input(\"\"))\n",
    "print(hcf(num1,num2))\n",
    "\n",
    "``` \n",
    "\n",
    "请补充完成hcf函数的定义。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共两行，每一行输入一个不超过1000的正整数。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，输出一个正整数。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "```\n",
    "6\n",
    "\n",
    "8\n",
    "```\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "```\n",
    "2\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 解法 1：从最大公约数的定义出发 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 32\n",
      " 24\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "def hcf(num1, num2):\n",
    "    factor1 = set()\n",
    "    factor2 = set()\n",
    "    \n",
    "    # 求 num1 的因子\n",
    "    for i in range(1, num1 + 1):\n",
    "        tmp1 = num1 // i\n",
    "        if i > tmp1:\n",
    "            break\n",
    "        elif i * tmp1 == num1:\n",
    "            factor1.add(i)\n",
    "            factor1.add(tmp1)\n",
    "    \n",
    "    # 求 num2 的因子\n",
    "    for i in range(1, num2 + 1):\n",
    "        tmp2 = num2 // i\n",
    "        if i > tmp2:\n",
    "            break\n",
    "        elif i * tmp2 == num2:\n",
    "            factor2.add(i)\n",
    "            factor2.add(tmp2)\n",
    "    \n",
    "    # 求两个数因子交集中最大数即为它们的最大公约数\n",
    "    return max(factor1 & factor2)\n",
    "\n",
    "\n",
    "num1 = int(input(\"\"))\n",
    "num2 = int(input(\"\"))\n",
    "print(hcf(num1, num2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 解法 2：利用更相减损法求最大公约数 (由 [@hitszjsy](https://github.com/hitszjsy) 同学提供)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "def hcf(num1, num2):\n",
    "    if num1 == num2:\n",
    "        return num1\n",
    "            if num1 > num2:\n",
    "        return hcf(num1 - num2, num2)\n",
    "    if num1 < num2:\n",
    "        return hcf(num1, num2 - num1)\n",
    "\n",
    "\n",
    "num1 = int(input(\"\"))\n",
    "num2 = int(input(\"\"))\n",
    "print(hcf(num1, num2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.求两个数的最小公倍数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "输入两个正整数num1和num2（不超过500），求它们的最小公倍数并输出。\n",
    "\n",
    "我们定义求最小公倍数的函数为lcm，给出程序主体如下：\n",
    "\n",
    "```python\n",
    "\n",
    "num1=int(input(\"\"))\n",
    "num2=int(input(\"\"))\n",
    "print(lcm(num1,num2))\n",
    "\n",
    "```\n",
    "\n",
    "请补充完成lcm函数的定义。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共两行，每一行输入一个不超过500的正整数。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，输出一个正整数。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "```\n",
    "4\n",
    "\n",
    "6\n",
    "```\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "```\n",
    "12\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 解法 1：利用公式法\n",
    "\n",
    "> 如果记 a 和 b 两个数的最大公约数为 (a, b)，最小公倍数为 [a, b]，则 (a, b) * [a, b] = a * b\n",
    "\n",
    "需要利用到上一题中求两数最大公约数的函数 `hcf`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 4\n",
      " 6\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\n"
     ]
    }
   ],
   "source": [
    "def lcm(num1, num2):\n",
    "    factor1 = set()\n",
    "    factor2 = set()\n",
    "    \n",
    "    # 求 num1 的因子\n",
    "    for i in range(1, num1 + 1):\n",
    "        tmp1 = num1 // i\n",
    "        if i > tmp1:\n",
    "            break\n",
    "        elif i * tmp1 == num1:\n",
    "            factor1.add(i)\n",
    "            factor1.add(tmp1)\n",
    "    \n",
    "    # 求 num2 的因子\n",
    "    for i in range(1, num2 + 1):\n",
    "        tmp2 = num2 // i\n",
    "        if i > tmp2:\n",
    "            break\n",
    "        elif i * tmp2 == num2:\n",
    "            factor2.add(i)\n",
    "            factor2.add(tmp2)\n",
    "    \n",
    "    # 求两个数因子交集中最大数即为它们的最大公约数\n",
    "    hcf2 = max(factor1 & factor2)\n",
    "    \n",
    "    # 利用公式法直接求解最小公倍数\n",
    "    return int(num1 * num2 / hcf2)\n",
    "\n",
    "\n",
    "num1 = int(input(\"\"))\n",
    "num2 = int(input(\"\"))\n",
    "print(lcm(num1, num2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 解法 2：分解质因数法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.求阶乘"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们定义求n（n为正整数且n<=20）的阶乘的函数为fact，给出程序主体如下：\n",
    "\n",
    "```python\n",
    "\n",
    "n=int(input(\"\"))\n",
    "print(fact(n))\n",
    "\n",
    "```\n",
    "\n",
    "请补充完成对fact函数的定义。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共一行，为一个小于20的正整数。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，为一个正整数。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "```\n",
    "3\n",
    "```\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "```\n",
    "6\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 4\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24\n"
     ]
    }
   ],
   "source": [
    "def fact(n):\n",
    "    tmp = 1\n",
    "    for i in range(1, n+1):\n",
    "        tmp *= i\n",
    "    return  tmp\n",
    "\n",
    "\n",
    "n = int(input(\"\"))\n",
    "print(fact(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.冒泡排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。\n",
    "\n",
    "已知输入为一个列表，列表中的元素都为整数，我们定义冒泡排序函数为bubbleSort，将列表中的元素按从小到大进行排序后得到一个新的列表并输出，给出程序主体如下：\n",
    "\n",
    "```python\n",
    "\n",
    "alist=list(map(int,input().split()))\n",
    "print(bubbleSort(alist))\n",
    "\n",
    "```\n",
    "\n",
    "请补充完成对bubbleSort函数的定义。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共一行，列表中的元素值，以空格隔开。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，为一个列表。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "```\n",
    "1 4 2 3\n",
    "```\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "```\n",
    "[1, 2, 3, 4]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1 2 4 3\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "def bubbleSort(a):\n",
    "    n = len(a)\n",
    "    for i in range(1, n):\n",
    "        for j in range(0, n-i):\n",
    "            if a[j+1] < a[j]:\n",
    "                a[j], a[j+1] = a[j+1], a[j]  # python 语法糖，不需要中间变量\n",
    "    return a\n",
    "            \n",
    "alist = list(map(int,input().split()))\n",
    "print(bubbleSort(alist))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Tips: 冒泡排序法在[菜鸟教程](https://www.runoob.com/w3cnote/bubble-sort.html)里有动图展示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**小结：**\n",
    "\n",
    "冒泡排序法是很经典的排序法，经常不写就容易忘或是犯各种各样的错误，主要注意的有以下几点：\n",
    "\n",
    "1. 注意数组的索引范围\n",
    "\n",
    "2. 虽然“冒泡法（升序）”意思是说小数往上浮的过程，但在实际写时，它表达的更像是**大数往下沉**的过程。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6.列表元素筛选"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "已知输入为一个列表，列表中的元素都为整数，我们定义元素筛选函数为foo，功能是检查获取传入列表对象的所有奇数位索引（注意列表的索引是从0开始的）对应的元素，并将其作为新列表返回给调用者。给出程序主体如下：\n",
    "\n",
    "```python\n",
    "\n",
    "alist=list(map(int,input().split()))\n",
    "print(foo(alist))\n",
    "\n",
    "```\n",
    "\n",
    "请补充完成对foo函数的定义。\n",
    "\n",
    "---\n",
    "\n",
    "**输入格式:**\n",
    "\n",
    "共一行，列表中的元素值，以空格隔开。\n",
    "\n",
    "**输出格式：**\n",
    "\n",
    "共一行，为一个列表。\n",
    "\n",
    "---\n",
    "\n",
    "**输入样例：**\n",
    "\n",
    "```\n",
    "1 2 3 4\n",
    "```\n",
    "\n",
    "**输出样例：**\n",
    "\n",
    "```\n",
    "[2, 4]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1 2 3 4\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 4]\n"
     ]
    }
   ],
   "source": [
    "def foo(alist):\n",
    "    n = len(alist)\n",
    "    tmp = []\n",
    "    \n",
    "    for i in range(n):\n",
    "        if i % 2 != 0:  # 奇数索引下标\n",
    "            tmp.append(alist[i])\n",
    "    \n",
    "    return tmp\n",
    "\n",
    "\n",
    "alist = list(map(int,input().split()))\n",
    "print(foo(alist))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}